package leetcode;

import java.util.Arrays;

public class Heaters {

	public int findRadius(int[] houses, int[] heaters) {
		if (houses == null || heaters == null || houses.length == 0
				|| heaters.length == 0) {
			return 0;
		}
		Arrays.sort(houses);
		Arrays.sort(heaters);
		if (heaters.length == 1) {
			return Math.max(Math.abs(heaters[0] - houses[0]),
					Math.abs(houses[houses.length - 1] - heaters[0]));
		}
		int firstHeater = heaters[0];
		int res = Math.abs(firstHeater - houses[0]);
		
		//一开始的思路错了， 想的是房子在heaters之间，但是其实不一定满足该条件
		//应该遍历houses,然后使用二分或者双指针来找到最近的两个heaters
		for (int i = 1; i < heaters.length; i++) {
			res = Math.max(res, (heaters[i] - firstHeater) / 2);
		}
		return res;
	}
	
	//use two pointers
	public int findRadius2(int[] houses, int[] heaters) {
		if (houses == null || heaters == null || houses.length == 0
				|| heaters.length == 0) {
			return 0;
		}
		Arrays.sort(houses);
		Arrays.sort(heaters);
		
		int res = Math.abs(0);
		
		int j = 0;
		for (int i = 0; i < houses.length; i++) {
			while (j < heaters.length - 1
					&& Math.abs(heaters[j + 1] - houses[i]) <= Math
							.abs(heaters[j] - houses[i])) {
				j++;
			}
			//也可以这样找，但是不是很懂这段
			//heaters[i] + heaters[i + 1] <= house * 2
			//is checking if house is closer to heaters[i] or heaters[i + 1]

			//The following same function is checking if house is less than half of the two heaters
			//If it is less than half, it is closer to the heaters[i] and vice versa
			//(heaters[i] + heaters[i + 1]) / 2 <= house

			//For example,
			//heaters[i] is at 2 while heaters[i+1] is at 6. half of 2 and 6 is 4. 
			//If house is less than 4 then it is closer to heaters[i] but if it is larger than 4, 
			//then it is closer to heaters[i+1]
//			while (j < heaters.length - 1
//					&& heaters[j] + heaters[j + 1] <= houses[i] * 2) {
//				j++;
//			}
			res = Math.max(res, Math.abs(heaters[j] - houses[i]));

		}
		return res;
	}
	
	/**
	 * binary search
	 */
	public int findRadius3(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int result = Integer.MIN_VALUE;
        
        for (int house : houses) {
        	//如果不包含该位置： (-(insertion point) - 1). 
        	//The insertion point is defined as the point at which the key would be inserted into the array: 
        	//the index of the first element greater than the key, 
        	//or a.length if all elements in the array are less than the specified key
            int index = Arrays.binarySearch(heaters, house);
            if (index < 0) {
            	//将index变为insertion point
            	index = -(index + 1);
            }
            
            //index的范围时0 ~ heaters.length，所以不会两者同时取1
            //意义是边界情况下，houses没有左取暖器或者右取暖器，但不会同时没有
            int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;
            int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
        
            result = Math.max(result, Math.min(dist1, dist2));
        }
        
        return result;
    }
}
